package com.堆排序;

public class Solution {
	public void swap(int a[] ,int i,int j) {
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	public int [] HeapSort(int [] array) {
		int len = array.length;
		if(len<1)return array;
		BuildMaxHeap(array);
		while(len>0) {
			swap(array,0,len-1);
			len--;
			AdjustDown(array, 0, len);
		}
		return array;
	}

	//建立大根堆
	public void BuildMaxHeap(int a[]) {
		int len = a.length;
		for(int i=(len-1)/2;i>=0;i--) {
			AdjustDown(a,i,len);
		}
	}
    //调整堆
	public void AdjustDown(int a[],int i,int len) {
		int maxi=i;
		if(i*2<len&&a[i*2]>a[maxi])
			maxi = i*2;
		if(i*2+1<len&&a[i*2+1]>a[maxi])
			maxi=i*2+1;
		//即父节点不是最大值被调换过了，那么还要递归下去对与父节点交换的那个节点
		if(maxi!=i) {
		  swap(a,i,maxi);
		  AdjustDown(a, maxi, len);//maxi指的是堆中最大的值
		}
	}
}
